The world is now full of databases. Some of these databases contain sensitive information on systems that are accessible from a network, such as the Internet. For example, credit card numbers, social security numbers, loan information, and medical information may all be available to authorized users in various databases. Sometimes, however, this sensitive information may become accessible to unauthorized users. For example, there have been many news stories about computer break-ins that compromise this sensitive information. One way to protect sensitive data is to encrypt the data before storing it in a database. This data, however, is often stored in databases that are served by software code that may make assumptions about the length, format, or both, of the various data items.
For example, credit card numbers and social security numbers may contain strings of decimal digits in a certain format, some dollar amounts may be limited to a certain range, some strings may only include alphabetic characters, and dates and zip codes may conform to a prescribed format or formats. It is generally not feasible to rewrite all this database code to support alternate formats, so it would be useful to encrypt data in a way that preserves its format well enough that the database code will still function properly and any validity checks that the code performs will still pass.
In cryptography, format-preserving encryption (FPE) refers to encrypting in such a way that the output (the ciphertext) is in the same format as the input (the plaintext). Several techniques for performing FPE are known. For example, one common approach is to use a Feistel or Luby-Rackoff scheme. The Feistel scheme is a method for adapting a block cipher, like AES, to produce a block cipher whose domain is closer in size to the number of elements in a given format. (The domain of, for example, AES is a power of 2128, which is not likely to be near the size of most formats to be encrypted.)
Feistel or Luby-Rackoff provides a way to obtain a cipher whose domain is close to a given size. Cycle walking is a technique for bridging the gap between the domain of a Feistel cipher and a format to encrypt. For example, a block cipher, such as AES, or more likely a block cipher derived from AES using a Feistel scheme, whose domain contains a format to encrypt, may be repeatedly applied to a plaintext from that format until the resultant ciphertext again lies in that format. Cycle walking has an advantage in that the elements of the desired format need not be mapped to a consecutive sequence of integers. Cycle walking, however, also has a disadvantage in that the number of iterations of the block cipher required for each FPE operation is unpredictable. For example, using cycle walking, the average the number of iterations of the block cipher is given by the size of domain of the block cipher divided by the number of elements in the format, but the actual number of iterations is random and may be quite large and is unpredictable.